{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Lines to Cover Points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #geometry #array #hash-table #math #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #几何 #数组 #哈希表 #数学 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumLines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #穿过所有点的所需最少直线数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <code>points</code>&nbsp;数组，<code>points[i] = [xi, yi]</code>&nbsp;表示直角坐标系 <strong>X-Y</strong> 的一个点。</p>\n",
    "\n",
    "<p>现在考虑向 X-Y 坐标系中添加 <strong>直线</strong>，使得每个点 <strong>至少</strong> 在一条直线上。</p>\n",
    "\n",
    "<p>返回能够穿过所有点的所需&nbsp;<strong>最少直线&nbsp;</strong>数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/01/23/image-20220123200023-1.png\" style=\"width: 350px; height: 402px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> points = [[0,1],[2,3],[4,5],[4,3]]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 所需最少直线数量为 2 ，一种可能的答案是添加:\n",
    "- 一条穿过点 (0, 1) 和 点(4, 5) 的直线\n",
    "- 另一条穿过点 (2, 3) 和点 (4, 3) 的直线\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/01/23/image-20220123200057-3.png\" style=\"width: 350px; height: 480px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> points = [[0,2],[-2,-2],[1,4]]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong> 所需最少直线数量为 1 ，唯一的答案是:\n",
    "- 一条穿过点 (-2, -2) 和点 (1, 4) 的直线\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= points.length &lt;= 10</code></li>\n",
    "\t<li><code>points[i].length == 2</code></li>\n",
    "\t<li><code>-100 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 100</code></li>\n",
    "\t<li><code>points</code>&nbsp;中元素都是唯一的</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-lines-to-cover-points](https://leetcode.cn/problems/minimum-number-of-lines-to-cover-points/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-lines-to-cover-points](https://leetcode.cn/problems/minimum-number-of-lines-to-cover-points/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[2,3],[4,5],[4,3]]', '[[0,2],[-2,-2],[1,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum((dx0*dy1!=dx1*dy0) for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, a: List[List[int]]) -> int:\n",
    "        a.sort()\n",
    "        py, px = 1 ,0\n",
    "        ans = 0\n",
    "        for i in range(1, len(a)):\n",
    "            dy =a[i][1]-a[i-1][1]\n",
    "            dx =a[i][0]-a[i-1][0]\n",
    "\n",
    "            if dy * px != dx * py:\n",
    "                ans +=1\n",
    "                py = dy\n",
    "                px = dx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n <= 2:\n",
    "            return n - 1\n",
    "        res = 1\n",
    "        for i in range(2,n):\n",
    "            dx0 = stockPrices[i-1][0] - stockPrices[i-2][0]\n",
    "            dy0 = stockPrices[i-1][1] - stockPrices[i-2][1]\n",
    "            dx1 = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            dy1 = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "\n",
    "            if dx0 * dy1 != dy0 * dx1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d0,p0 = stockPrices[0]\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d10,p10 = d1-d0,p1-p0\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d21,p21 = d2-d1,p2-p1\n",
    "            if d21*p10!=d10*p21:\n",
    "                mls += 1\n",
    "            d1,p1 = d2,p2\n",
    "            d10,p10 = d21,p21\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices) <= 1:\n",
    "            return 0\n",
    "        stockPrices.sort(key=lambda x: x[0])\n",
    "        ans = 1\n",
    "        for i in range(2, len(stockPrices)):\n",
    "            x1, y1 = stockPrices[i - 2]\n",
    "            x2, y2 = stockPrices[i - 1]\n",
    "            x3, y3 = stockPrices[i]\n",
    "            if (x2 - x1) * (y3 - y2) != (x3 - x2) * (y2 - y1):\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        def slope(p1: List[int], p2: List[int]) -> Tuple[int, int]:\n",
    "            x1, y1 = p1; x2, y2 = p2\n",
    "            gcd_ = gcd(y2 - y1, x2 - x1)\n",
    "\n",
    "            return (y2 - y1) // gcd_,  (x2 - x1) // gcd_\n",
    "        n = len(stockPrices)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        stockPrices.sort()\n",
    "        p1 = stockPrices[0]\n",
    "        p2 = stockPrices[1]\n",
    "        slope1 = slope(p1, p2)\n",
    "        res = 1\n",
    "        for i in range(2, n):\n",
    "            p3 = stockPrices[i]\n",
    "            slope2 = slope(p2, p3)\n",
    "            if slope1[0] != slope2[0] or slope1[1] != slope2[1]:\n",
    "                res += 1\n",
    "            slope1, p1, p2 = slope2, p2, p3\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        def slope(p1: List[int], p2: List[int]) -> Tuple[int, int]:\n",
    "            x1, y1 = p1; x2, y2 = p2\n",
    "            gcd_ = gcd(y2 - y1, x2 - x1)\n",
    "            return (y2 - y1) // gcd_,  (x2 - x1) // gcd_\n",
    "        n = len(stockPrices)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        stockPrices.sort()\n",
    "        p1 = stockPrices[0]\n",
    "        p2 = stockPrices[1]\n",
    "        slope1 = slope(p1, p2)\n",
    "        res = 1\n",
    "        for i in range(2, n):\n",
    "            p3 = stockPrices[i]\n",
    "            slope2 = slope(p2, p3)\n",
    "            if slope1[0] != slope2[0] or slope1[1] != slope2[1]:\n",
    "                res += 1\n",
    "            slope1, p1, p2 = slope2, p2, p3\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        l = len(stockPrices)\n",
    "        mls = int(l>1)\n",
    "        for i in range(l-2):\n",
    "            if (stockPrices[i+2][0]-stockPrices[i+1][0])*(stockPrices[i+1][1]-stockPrices[i][1])!=(stockPrices[i+1][0]-stockPrices[i][0])*(stockPrices[i+2][1]-stockPrices[i+1][1]):\n",
    "                mls += 1\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def judge(x1,y1,x2,y2,x3,y3):\n",
    "    return (x2-x1)*(y3-y1)==(x3-x1)*(y2-y1)\n",
    "class Solution:\n",
    "    def minimumLines(self, arr: List[List[int]]) -> int:\n",
    "        n=len(arr)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        if n==2:\n",
    "            return 1\n",
    "        arr.sort(key=lambda x:x[0])\n",
    "        res=1\n",
    "        for i in range(2,n):\n",
    "            x1,y1=arr[i-2]\n",
    "            x2,y2=arr[i-1]\n",
    "            x3,y3=arr[i]\n",
    "            if not judge(x1,y1,x2,y2,x3,y3):\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n <= 2:\n",
    "            return n - 1\n",
    "        res = 1\n",
    "        for i in range(2, n):\n",
    "            # 遍历相邻点对，并判断线段是否可以合并\n",
    "            dx0 = stockPrices[i-1][0] - stockPrices[i-2][0]\n",
    "            dy0 = stockPrices[i-1][1] - stockPrices[i-2][1]\n",
    "            dx1 = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            dy1 = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "            if dx0 * dy1 != dy0 * dx1:\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/minimum-lines-to-represent-a-line-chart/solutions/1538682/biao-shi-yi-ge-zhe-xian-tu-de-zui-shao-x-gwnk/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum((dx0*dy1!=dx1*dy0) for (dx0,dy0),(dx1,dy1) in pairwise(((x2-x1),(y2-y1)) for (x1,y1),(x2,y2) in pairwise(stockPrices)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        l = len(stockPrices)\n",
    "        return (l>1)+sum((stockPrices[i+1][0]-stockPrices[i][0])*(stockPrices[i][1]-stockPrices[i-1][1])!=(stockPrices[i][0]-stockPrices[i-1][0])*(stockPrices[i+1][1]-stockPrices[i][1]) for i in range(1,l-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from decimal import Decimal\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort(key=lambda x: x[0])\n",
    "        ans, pre_dy, pre_dx = 0, 1, 0\n",
    "        for (x1, y1), (x2, y2) in pairwise(stockPrices):\n",
    "            dy, dx = y2 - y1, x2 - x1\n",
    "            if dy * pre_dx != pre_dy * dx:\n",
    "                ans += 1\n",
    "                pre_dy, pre_dx = dy, dx\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, a: List[List[int]]) -> int:\n",
    "        a.sort()\n",
    "        prex, prey = 0, 1 \n",
    "        ans = 0\n",
    "        n = len(a)\n",
    "        for i in range(1, n):\n",
    "            dy = a[i][1] - a[i - 1][1]\n",
    "            dx = a[i][0] - a[i - 1][0]\n",
    "\n",
    "            if dy * prex != dx * prey:\n",
    "                ans += 1\n",
    "                prex, prey = dx, dy \n",
    "        return ans \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        n, nums = len(stockPrices), sorted(stockPrices)\n",
    "        res, dv, dd = 0, None, None\n",
    "        for i in range(1,n):\n",
    "            tv, td = (nums[i][1]-nums[i-1][1]), (nums[i][0]-nums[i-1][0])\n",
    "            if not dd or tv * dd != td * dv:\n",
    "                res, dv, dd = res+1, tv, td\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        ans=1\n",
    "        n=len(stockPrices)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        stockPrices.sort(key=lambda x:x[0])\n",
    "        for i in range(1,n-1):\n",
    "          a=stockPrices[i-1]  \n",
    "          x=stockPrices[i]\n",
    "          y=stockPrices[i+1]\n",
    "          if (x[1]-a[1])*(y[0]-x[0])!=(y[1]-x[1])*(x[0]-a[0]):\n",
    "             ans+=1\n",
    "        return ans      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n <= 2:\n",
    "            return n - 1\n",
    "        res = 1\n",
    "        for i in range(2, n):\n",
    "            dx0 = stockPrices[i-1][0] - stockPrices[i-2][0]\n",
    "            dy0 = stockPrices[i-1][1] - stockPrices[i-2][1]\n",
    "            dx1 = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            dy1 = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "            if dx0 * dy1 != dy0 * dx1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from decimal import Decimal\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        ans, pre_dy, pre_dx = 0, 1, 0\n",
    "        for (x1, y1), (x2, y2) in pairwise(stockPrices):\n",
    "            dy, dx = y2 - y1, x2 - x1\n",
    "            if dy * pre_dx != pre_dy * dx:\n",
    "                ans += 1\n",
    "                pre_dy, pre_dx = dy, dx\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        l = len(stockPrices)\n",
    "        return (l>1)+sum((stockPrices[i+2][0]-stockPrices[i+1][0])*(stockPrices[i+1][1]-stockPrices[i][1])!=(stockPrices[i+1][0]-stockPrices[i][0])*(stockPrices[i+2][1]-stockPrices[i+1][1]) for i in range(l-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n <= 2:\n",
    "            return n - 1\n",
    "        res = 1\n",
    "        for i in range(2, n):\n",
    "            # 遍历相邻点对，并判断线段是否可以合并\n",
    "            dx0 = stockPrices[i-1][0] - stockPrices[i-2][0]\n",
    "            dy0 = stockPrices[i-1][1] - stockPrices[i-2][1]\n",
    "            dx1 = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            dy1 = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "            if dx0 * dy1 != dy0 * dx1:\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices) == 1:\n",
    "            return 0\n",
    "        ans = 1\n",
    "        stockPrices.sort()\n",
    "        for i in range(len(stockPrices) - 2):\n",
    "            k1 = (stockPrices[i][1] - stockPrices[i + 1][1]) * (stockPrices[i + 1][0] - stockPrices[i + 2][0])\n",
    "            k2 = (stockPrices[i + 1][1] - stockPrices[i + 2][1]) * (stockPrices[i][0] - stockPrices[i + 1][0])\n",
    "            if k1 != k2:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        mls = int(len(stockPrices)>1)\n",
    "        for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(stockPrices)):\n",
    "            if dx0*dy1!=dx1*dy0:\n",
    "                mls += 1\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        res,dx,dy=0,0,1\n",
    "        for (x1,y1),(x2,y2) in pairwise(stockPrices):\n",
    "            if dx*(y2-y1)!=dy*(x2-x1): res +=1\n",
    "            dx,dy=x2-x1,y2-y1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        l = len(stockPrices)\n",
    "        if l==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        i1,j1 = stockPrices[0]\n",
    "        i2,j2 = stockPrices[1]\n",
    "        i21,j21 = i2-i1,j2-j1\n",
    "        for i in range(2,l):\n",
    "            i3,j3 = stockPrices[i]\n",
    "            i32,j32 = i3-i2,j3-j2\n",
    "            if i32*j21!=i21*j32:\n",
    "                mls += 1\n",
    "            i2,j2 = i3,j3\n",
    "            i21,j21 = i32,j32\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        ret  = n-1\n",
    "        for i in range(1, n-1):\n",
    "            dx1, dx2 = stockPrices[i][0] - stockPrices[i-1][0], stockPrices[i+1][0] - stockPrices[i][0]\n",
    "            dy1, dy2 = stockPrices[i][1] - stockPrices[i-1][1], stockPrices[i+1][1] - stockPrices[i][1]\n",
    "            if dx1 * dy2 == dy1 * dx2:\n",
    "                ret -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        mls,pre_dy,pre_dx = 0,1,0\n",
    "        for (x1,y1),(x2,y2) in pairwise(stockPrices):\n",
    "            dy,dx = y2-y1,x2-x1\n",
    "            if dy*pre_dx!=pre_dy*dx:\n",
    "                mls += 1\n",
    "                pre_dy,pre_dx = dy,dx\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort(key = lambda x: x[0])\n",
    "        ans = 0\n",
    "        pre = [1, inf]\n",
    "        for i in range(1, len(stockPrices)):\n",
    "            if (stockPrices[i][1] - stockPrices[i-1][1]) * pre[0] != pre[1] * (stockPrices[i][0] - stockPrices[i-1][0]):\n",
    "                ans += 1\n",
    "                pre = [stockPrices[i][0] - stockPrices[i-1][0], stockPrices[i][1] - stockPrices[i-1][1]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        return (len(stockPrices)>1)+sum(1 for (dx0,dy0),(dx1,dy1) in pairwise(((x1-x0),(y1-y0)) for (x0,y0),(x1,y1) in pairwise(sorted(stockPrices))) if dx0*dy1!=dx1*dy0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n <= 2:\n",
    "            return n - 1\n",
    "        res = 1\n",
    "        for i in range(2,n):\n",
    "            dx0 = stockPrices[i-1][0] - stockPrices[i-2][0]\n",
    "            dy0 = stockPrices[i-1][1] - stockPrices[i-2][1]\n",
    "            dx1 = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            dy1 = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "\n",
    "            if dx0 * dy1 != dy0 * dx1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        L = len(stockPrices)\n",
    "        if L == 1: return 0 \n",
    "        if L == 2: return 1 \n",
    "\n",
    "        stockPrices = sorted(stockPrices)\n",
    "        line = 1 \n",
    "        for idx in range(2, L): \n",
    "            x1, y1 = stockPrices[idx - 2]\n",
    "            x2, y2 = stockPrices[idx - 1]\n",
    "            x3, y3 = stockPrices[idx]\n",
    "\n",
    "            if (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1): \n",
    "                line += 1 \n",
    "\n",
    "        return line \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        res=0\n",
    "        for i,(x,y) in enumerate(stockPrices):\n",
    "            if i==0: continue\n",
    "            if i==1 or (y-stockPrices[i-1][1])*(x-stockPrices[i-2][0])!=(y-stockPrices[i-2][1])*(x-stockPrices[i-1][0]): res +=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        it = ((v2-v1, d2-d1) for (d1, v1), (d2, v2) in zip(stockPrices, stockPrices[1:]))\n",
    "        v,d = 1, 0\n",
    "        result = 0\n",
    "        for dv, dd in it:\n",
    "            if v*dd != dv*d: result += 1\n",
    "            v, d = dv, dd\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices) == 1:\n",
    "            return 0\n",
    "        ret = 1\n",
    "        stockPrices.sort()\n",
    "        for i in range(2, len(stockPrices)):\n",
    "            y1 = stockPrices[i - 1][1] - stockPrices[i - 2][1]\n",
    "            x1 = stockPrices[i - 1][0] - stockPrices[i - 2][0]\n",
    "            \n",
    "            y2 = stockPrices[i][1] - stockPrices[i - 1][1]\n",
    "            x2 = stockPrices[i][0] - stockPrices[i - 1][0]\n",
    "            \n",
    "            if y1 * x2 != y2 * x1:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        mls,pre_dx,pre_dy = 0,0,1\n",
    "        for (x1,y1),(x2,y2) in pairwise(stockPrices):\n",
    "            dy,dx = y2-y1,x2-x1\n",
    "            if dy*pre_dx!=pre_dy*dx:\n",
    "                mls += 1\n",
    "                pre_dy,pre_dx = dy,dx\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices) == 1:\n",
    "            return 0\n",
    "        answer = 1 \n",
    "        stockPrices.sort(key=lambda x:x[0])\n",
    "        pre_dy, pre_dx = stockPrices[1][1] - stockPrices[0][1], stockPrices[1][0] - stockPrices[0][0]\n",
    "        pre_y, pre_x = stockPrices[1][1], stockPrices[1][0]\n",
    "        for stockPrice in stockPrices[2:]:\n",
    "            dy, dx = stockPrice[1] - pre_y, stockPrice[0] - pre_x\n",
    "            if dy * pre_dx != pre_dy * dx:\n",
    "                answer += 1 \n",
    "                pre_dy, pre_dx = dy, dx\n",
    "            pre_y, pre_x = stockPrice[1], stockPrice[0]\n",
    "        return answer\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from decimal import Decimal\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        ans = 0\n",
    "        last = None\n",
    "        for (x1, y1), (x2, y2) in pairwise(stockPrices):\n",
    "            # x值不可能相同，因此除以x的差\n",
    "            new = Decimal(y2 - y1) / (x2 - x1)\n",
    "            if new != last:\n",
    "                ans += 1\n",
    "                last = new\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        n = len(stockPrices)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        ans = 1\n",
    "        x, y = stockPrices[1][0] - stockPrices[0][0], stockPrices[1][1] - stockPrices[0][1]\n",
    "        for i in range(2, n):\n",
    "            xi, yi = stockPrices[i][0] - stockPrices[i - 1][0], stockPrices[i][1] - stockPrices[i - 1][1]\n",
    "            if xi * y != yi * x:\n",
    "                ans += 1\n",
    "                x, y = xi, yi\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from decimal import Decimal\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort(key=itemgetter(0))\n",
    "        ans, pre_dy, pre_dx = 0, 1, 0\n",
    "        for (x1, y1), (x2, y2) in pairwise(stockPrices):\n",
    "            dy, dx = y2 - y1, x2 - x1\n",
    "            if dy * pre_dx != pre_dy * dx:\n",
    "                ans += 1\n",
    "                pre_dy, pre_dx = dy, dx\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, s: List[List[int]]) -> int:\n",
    "        s.sort()\n",
    "        if len(s) == 1:\n",
    "            return 0\n",
    "        if len(s) == 2:\n",
    "            return 1\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        for i in range(2, len(s)):\n",
    "            x1, y1 = s[i - 2]\n",
    "            x2, y2 = s[i - 1]\n",
    "            x3, y3 = s[i]\n",
    "            if (x1 - x2) * (y3 - y1) != (y1 - y2) * (x3 - x1):\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stock: List[List[int]]) -> int:\n",
    "        stock.sort()\n",
    "        pre = (-1, -1)\n",
    "        ans = 0\n",
    "        for (x, y), (a, b) in pairwise(stock):\n",
    "            if x == a:\n",
    "                cur = (x, -1)\n",
    "            else:\n",
    "                g = math.gcd(b-y, a-x)\n",
    "                bb = (b-y)//g\n",
    "                aa = (a-x)//g\n",
    "                if aa < 0:\n",
    "                    aa *= -1\n",
    "                    bb *= -1\n",
    "                cur = (bb, aa)\n",
    "            ans += pre != cur\n",
    "            pre = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        from fractions import Fraction\n",
    "        stockPrices.sort()\n",
    "        pre_teng=math.inf\n",
    "        ans = 0\n",
    "        n= len (stockPrices)\n",
    "\n",
    "        for i in range(1,n):\n",
    "            dy = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "            dx = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            if Fraction(dy,dx) != pre_teng:\n",
    "                ans += 1\n",
    "                pre_teng = Fraction(dy,dx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "\n",
    "        if len(stockPrices) == 1:\n",
    "            return 0\n",
    "        if len(stockPrices) == 2:\n",
    "            return 1\n",
    "\n",
    "        cnt = 1\n",
    "\n",
    "        day2, price2 = stockPrices[1]\n",
    "        day1, price1 = stockPrices[0]\n",
    "\n",
    "        dx0 = day2 - day1\n",
    "        dy0 = price2 - price1\n",
    "\n",
    "        for i in range(2,len(stockPrices)):\n",
    "            day2, price2 = stockPrices[i]\n",
    "            day1, price1 = stockPrices[i-1]\n",
    "                \n",
    "            dx1 = day2 - day1\n",
    "            dy1 = price2 - price1\n",
    "\n",
    "\n",
    "            if dy0*dx1 != dx0 * dy1:\n",
    "                cnt += 1\n",
    "                dx0 = dx1\n",
    "                dy0 = dy1\n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        from fractions import Fraction\n",
    "        stockPrices.sort()\n",
    "        pre_teng=math.inf\n",
    "        ans = 0\n",
    "        n= len (stockPrices)\n",
    "\n",
    "        for i in range(1,n):\n",
    "            dy = stockPrices[i][1] - stockPrices[i-1][1]\n",
    "            dx = stockPrices[i][0] - stockPrices[i-1][0]\n",
    "            if Fraction(dy,dx) != pre_teng:\n",
    "                ans += 1\n",
    "                pre_teng = Fraction(dy,dx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        l = len(stockPrices)\n",
    "        if l==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        i0,j0 = stockPrices[0]\n",
    "        i1,j1 = stockPrices[1]\n",
    "        i10,j10 = i1-i0,j1-j0\n",
    "        for i in range(2,l):\n",
    "            i2,j2 = stockPrices[i]\n",
    "            i21,j21 = i2-i1,j2-j1\n",
    "            if i21*j10!=i10*j21:\n",
    "                mls += 1\n",
    "            i1,j1 = i2,j2\n",
    "            i10,j10 = i21,j21\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, s: List[List[int]]) -> int:\n",
    "        s.sort()\n",
    "        if len(s) == 1:\n",
    "            return 0\n",
    "        if len(s) == 2:\n",
    "            return 1\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        for i in range(2, len(s)):\n",
    "            x1, y1 = s[i - 2]\n",
    "            x2, y2 = s[i - 1]\n",
    "            x3, y3 = s[i]\n",
    "            if (x1 - x2) * (y3 - y1) != (y1 - y2) * (x3 - x1):\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        l = len(stockPrices)\n",
    "        if l==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        i1,o1 = stockPrices[0]\n",
    "        i2,o2 = stockPrices[1]\n",
    "        i21,o21 = i2-i1,o2-o1\n",
    "        for i in range(2,l):\n",
    "            i3,o3 = stockPrices[i]\n",
    "            i32,o32 = i3-i2,o3-o2\n",
    "            if i32*o21!=i21*o32:\n",
    "                mls += 1\n",
    "            i2,o2 = i3,o3\n",
    "            i21,o21 = i32,o32\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        # 从第三点开始，斜率不同就加1\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        \n",
    "        ans = 1\n",
    "        for i in range(2, n):\n",
    "            x1, y1 = stockPrices[i-2]\n",
    "            x2, y2 = stockPrices[i-1]\n",
    "            x3, y3 = stockPrices[i]\n",
    "            if (y1-y2) * (x3-x2) != (y3-y2) * (x1-x2):\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        stack = []\n",
    "        n = len(stockPrices)\n",
    "        for i in range(1, n):\n",
    "            x, y = stockPrices[i-1]\n",
    "            a, b = stockPrices[i]\n",
    "            if x == a:\n",
    "                cur = (x, -1)\n",
    "            else:\n",
    "                g = math.gcd(b-y, a-x)\n",
    "                bb = (b-y)//g\n",
    "                aa = (a-x)//g\n",
    "                if aa < 0:\n",
    "                    aa *= -1\n",
    "                    bb *= -1\n",
    "\n",
    "                cur = (bb, aa)\n",
    "            if stack and stack[-1] == cur:\n",
    "                continue\n",
    "            stack.append(cur)\n",
    "        return len(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\r\n",
    "        # sort stockPrices by x\r\n",
    "        stockPrices.sort(key=lambda x: x[0])\r\n",
    "        res = len(stockPrices) - 1\r\n",
    "        if len(stockPrices) == 1:\r\n",
    "            return res\r\n",
    "\r\n",
    "        start_point = stockPrices[0]\r\n",
    "        for i, _price in enumerate(stockPrices):\r\n",
    "            if i == 0:\r\n",
    "                continue\r\n",
    "            if _price == stockPrices[-1]:\r\n",
    "                return res\r\n",
    "\r\n",
    "            if (stockPrices[i + 1][1] - stockPrices[i][1]) * (start_point[0] - stockPrices[i][0]) == (stockPrices[i + 1][0] - stockPrices[i][0]) * (start_point[1] - stockPrices[i][1]):\r\n",
    "                res -= 1\r\n",
    "                print(i, _price, res, start_point, \"same\")\r\n",
    "                # continue\r\n",
    "            else:\r\n",
    "                start_point = _price\r\n",
    "                print(i, _price, res, start_point, \"diff\")\r\n",
    "                # continue\r\n",
    "\r\n",
    "        return res\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from decimal import Decimal\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        ans = 0\n",
    "        last = None\n",
    "        for (x1, y1), (x2, y2) in pairwise(stockPrices):\n",
    "            # x值不可能相同，因此除以x的差\n",
    "            new = Decimal(y2 - y1) / Decimal(x2 - x1)\n",
    "            if new != last:\n",
    "                ans += 1\n",
    "                last = new\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        n = len(stockPrices)\n",
    "        if n == 1: return 0\n",
    "        res = 1\n",
    "        c,d,e,f = stockPrices[0][0],stockPrices[0][1],stockPrices[1][0],stockPrices[1][1]\n",
    "        for i in range(2,n):\n",
    "            a,b,c,d,e,f = c,d,e,f,stockPrices[i][0],stockPrices[i][1]\n",
    "            if (c-a)*(f-b) != (d-b)*(e-a): res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)<3:\n",
    "            return len(stockPrices)-1\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d1_0,p1_0 = d1-stockPrices[0][0],p1-stockPrices[0][1]\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d2_1,p2_1 = d2-d1,p2-p1\n",
    "            if d2_1*p1_0!=d1_0*p2_1:\n",
    "                mls += 1\n",
    "                d1_0,p1_0 = d2_1,p2_1\n",
    "            d1,p1 = d2,p2\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d1_0,p1_0 = d1-stockPrices[0][0],p1-stockPrices[0][1]\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d2_1,p2_1 = d2-d1,p2-p1\n",
    "            if d2_1*p1_0!=d1_0*p2_1:\n",
    "                mls += 1\n",
    "            d1,p1 = d2,p2\n",
    "            d1_0,p1_0 = d2_1,p2_1\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        stockPrices.sort()\n",
    "        if len(stockPrices) == 1:return 0\n",
    "        if len(stockPrices) == 2:return 1\n",
    "        res = 1\n",
    "        n = len(stockPrices)\n",
    "        A,B = stockPrices[0],stockPrices[1]\n",
    "        for i in range(2,n):\n",
    "            C = stockPrices[i]\n",
    "            if (B[0]-A[0])*(C[1]-B[1]) != (B[1]-A[1])*(C[0]-B[0]):\n",
    "                res += 1\n",
    "            A = B\n",
    "            B = C\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d10,p10 = d1-stockPrices[0][0],p1-stockPrices[0][1]\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d21,p21 = d2-d1,p2-p1\n",
    "            mls += d21*p10!=d10*p21\n",
    "            d1,p1 = d2,p2\n",
    "            d10,p10 = d21,p21\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        i0,j0 = stockPrices[0]\n",
    "        i1,j1 = stockPrices[1]\n",
    "        i10,j10 = i1-i0,j1-j0\n",
    "        for p in stockPrices[2:]:\n",
    "            i2,j2 = p\n",
    "            i21,j21 = i2-i1,j2-j1\n",
    "            if i21*j10!=i10*j21:\n",
    "                mls += 1\n",
    "            i1,j1 = i2,j2\n",
    "            i10,j10 = i21,j21\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d0,p0 = stockPrices[0]\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d10,p10 = d1-d0,p1-p0\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d21,p21 = d2-d1,p2-p1\n",
    "            mls += d21*p10!=d10*p21\n",
    "            d1,p1 = d2,p2\n",
    "            d10,p10 = d21,p21\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices) == 1:\n",
    "            return 0\n",
    "        ans = 1\n",
    "        stockPrices.sort(key=lambda c:c[0])\n",
    "        for i in range(len(stockPrices) - 2):\n",
    "            k1 = (stockPrices[i][1] - stockPrices[i + 1][1]) * (stockPrices[i + 1][0] - stockPrices[i + 2][0])\n",
    "            k2 = (stockPrices[i + 1][1] - stockPrices[i + 2][1]) * (stockPrices[i][0] - stockPrices[i + 1][0])\n",
    "            if k1 != k2:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)<3:\n",
    "            return len(stockPrices)-1\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d1_0,p1_0 = d1-stockPrices[0][0],p1-stockPrices[0][1]\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d2_1,p2_1 = d2-d1,p2-p1\n",
    "            if d2_1*p1_0!=d1_0*p2_1:\n",
    "                mls += 1\n",
    "            d1,p1 = d2,p2\n",
    "            d1_0,p1_0 = d2_1,p2_1\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices) == 1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        px, py = stockPrices[1][0] - stockPrices[0][0], stockPrices[1][1] - stockPrices[0][1]\n",
    "        g = gcd(px, py)\n",
    "        px //= g\n",
    "        py //= g\n",
    "        ans = 1\n",
    "        for i in range(2, len(stockPrices)):\n",
    "            dx, dy = stockPrices[i][0] - stockPrices[i - 1][0], stockPrices[i][1] - stockPrices[i - 1][1]\n",
    "            g = gcd(dx, dy)\n",
    "            dx //= g\n",
    "            dy //= g\n",
    "            if (dx, dy) != (px, py):\n",
    "                px, py = dx, dy\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, stockPrices: List[List[int]]) -> int:\n",
    "        if len(stockPrices)==1:\n",
    "            return 0\n",
    "        stockPrices.sort()\n",
    "        mls = 1\n",
    "        d1,p1 = stockPrices[1]\n",
    "        d10,p10 = d1-stockPrices[0][0],p1-stockPrices[0][1]\n",
    "        for d2,p2 in stockPrices[2:]:\n",
    "            d21,p21 = d2-d1,p2-p1\n",
    "            if d21*p10!=d10*p21:\n",
    "                mls += 1\n",
    "            d1,p1 = d2,p2\n",
    "            d10,p10 = d21,p21\n",
    "        return mls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Set\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "# 1 <= points.length <= 10\n",
    "class Solution:\n",
    "    def minimumLines(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n in (1, 2):\n",
    "            return 1\n",
    "\n",
    "        bestLines = self.bestLine(points)\n",
    "        res = 0x3F3F3F3F\n",
    "        for selectedIds in bestLines:\n",
    "            remainIds = set(range(n)) - selectedIds\n",
    "            res = min(res, 1 + self.minimumLines([points[i] for i in remainIds]))\n",
    "        return res\n",
    "\n",
    "    @staticmethod\n",
    "    def bestLine(points: List[List[int]]) -> List[Set[int]]:\n",
    "        \"\"\"求出通过点数最多的所有直线\"\"\"\n",
    "\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "\n",
    "        n = len(points)\n",
    "        res = []\n",
    "        maxCount = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i]\n",
    "            groups = defaultdict(set)\n",
    "\n",
    "            for j in range(i + 1, n):\n",
    "                x2, y2 = points[j]\n",
    "                A, B = y2 - y1, x2 - x1\n",
    "                if B == 0:\n",
    "                    key = (0, 0)\n",
    "                else:\n",
    "                    gcd_ = gcd(A, B)\n",
    "                    key = (A / gcd_, B / gcd_)\n",
    "\n",
    "                groups[key].add(j)\n",
    "                count = len(groups[key])\n",
    "                if count > maxCount:\n",
    "                    maxCount = count\n",
    "                    res = [groups[key] | {i}]\n",
    "                elif count == maxCount:\n",
    "                    res.append(groups[key] | {i})\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "\n",
    "        def get_line(x, y):\n",
    "            if x[0] == y[0]:\n",
    "                return [inf, x[0]]\n",
    "            k = (y[1] - x[1]) / (y[0] - x[0])\n",
    "            b = y[1] - k * y[0]\n",
    "            return k, b \n",
    "        \n",
    "        def is_inline(x, k, b):\n",
    "            if k == inf:\n",
    "                return x[0] == b \n",
    "            return x[1] == k * x[0] + b \n",
    "\n",
    "        @cache\n",
    "        def f(mask):\n",
    "            if mask.bit_count() == n:\n",
    "                return 0\n",
    "            if mask.bit_count() >= n - 2:\n",
    "                return 1\n",
    "            start = -1\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1 == 0:\n",
    "                    start = i \n",
    "                    break \n",
    "            tmp = mask ^ (1 << start)\n",
    "            res = inf \n",
    "            for i in range(start + 1, n):\n",
    "                if (mask >> i) & 1 == 0:\n",
    "                    tmp1 = tmp \n",
    "                    tmp1 ^= (1 << i)\n",
    "                    k, b = get_line(points[start], points[i])\n",
    "                    for j in range(start + 1, n):\n",
    "                        if (tmp1 >> j) & 1 == 0 and is_inline(points[j], k, b):\n",
    "                            tmp1 ^= (1 << j)\n",
    "                    res = min(res, f(tmp1) + 1)\n",
    "            return res \n",
    "\n",
    "        return f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Set\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "# 1 <= points.length <= 10\n",
    "class Solution:\n",
    "    def minimumLines(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n in (1, 2):\n",
    "            return 1\n",
    "\n",
    "        bestLines = self.bestLine(points)\n",
    "        res = 0x3F3F3F3F\n",
    "        for selectedIds in bestLines:\n",
    "            remainIds = set(range(n)) - selectedIds\n",
    "            res = min(res, 1 + self.minimumLines([points[i] for i in remainIds]))\n",
    "        return res\n",
    "\n",
    "    @staticmethod\n",
    "    def bestLine(points: List[List[int]]) -> List[Set[int]]:\n",
    "        \"\"\"求出通过点数最多的所有直线\"\"\"\n",
    "\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "\n",
    "        n = len(points)\n",
    "        res = []\n",
    "        maxCount = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i]\n",
    "            groups = defaultdict(set)\n",
    "\n",
    "            for j in range(i + 1, n):\n",
    "                x2, y2 = points[j]\n",
    "                A, B = y2 - y1, x2 - x1\n",
    "                if B == 0:\n",
    "                    key = (0, 0)\n",
    "                else:\n",
    "                    gcd_ = gcd(A, B)\n",
    "                    key = (A / gcd_, B / gcd_)\n",
    "\n",
    "                groups[key].add(j)\n",
    "                count = len(groups[key])\n",
    "                if count > maxCount:\n",
    "                    maxCount = count\n",
    "                    res = [groups[key] | {i}]\n",
    "                elif count == maxCount:\n",
    "                    res.append(groups[key] | {i})\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Set\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "# 1 <= points.length <= 10\n",
    "class Solution:\n",
    "    def minimumLines(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n in (1, 2):\n",
    "            return 1\n",
    "\n",
    "        bestLines = self.bestLine(points)\n",
    "        res = 0x3F3F3F3F\n",
    "        for selectedIds in bestLines:\n",
    "            remainIds = set(range(n)) - selectedIds\n",
    "            res = min(res, 1 + self.minimumLines([points[i] for i in remainIds]))\n",
    "        return res\n",
    "\n",
    "    @staticmethod\n",
    "    def bestLine(points: List[List[int]]) -> List[Set[int]]:\n",
    "        \"\"\"求出通过点数最多的所有直线\"\"\"\n",
    "\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "\n",
    "        n = len(points)\n",
    "        res = []\n",
    "        maxCount = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i]\n",
    "            groups = defaultdict(set)\n",
    "\n",
    "            for j in range(i + 1, n):\n",
    "                x2, y2 = points[j]\n",
    "                A, B = y2 - y1, x2 - x1\n",
    "                if B == 0:\n",
    "                    key = (0, 0)\n",
    "                else:\n",
    "                    gcd_ = gcd(A, B)\n",
    "                    key = (A / gcd_, B / gcd_)\n",
    "\n",
    "                groups[key].add(j)\n",
    "                count = len(groups[key])\n",
    "                if count > maxCount:\n",
    "                    maxCount = count\n",
    "                    res = [groups[key] | {i}]\n",
    "                elif count == maxCount:\n",
    "                    res.append(groups[key] | {i})\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "\n",
    "        def get_line(x, y):\n",
    "            if x[0] == y[0]:\n",
    "                return [inf, x[0]]\n",
    "            k = (y[1] - x[1]) / (y[0] - x[0])\n",
    "            b = y[1] - k * y[0]\n",
    "            return k, b \n",
    "        \n",
    "        def is_inline(x, k, b):\n",
    "            if k == inf:\n",
    "                return x[0] == b \n",
    "            return x[1] == k * x[0] + b \n",
    "\n",
    "        @cache\n",
    "        def f(mask):\n",
    "            if mask.bit_count() == n:\n",
    "                return 0\n",
    "            if mask.bit_count() >= n - 2:\n",
    "                return 1\n",
    "            start = -1\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1 == 0:\n",
    "                    start = i \n",
    "                    break \n",
    "            tmp = mask ^ (1 << start)\n",
    "            res = inf \n",
    "            for i in range(start + 1, n):\n",
    "                if (mask >> i) & 1 == 0:\n",
    "                    tmp1 = tmp \n",
    "                    tmp1 ^= (1 << i)\n",
    "                    k, b = get_line(points[start], points[i])\n",
    "                    for j in range(start + 1, n):\n",
    "                        if (tmp1 >> j) & 1 == 0 and is_inline(points[j], k, b):\n",
    "                            tmp1 ^= (1 << j)\n",
    "                    res = min(res, f(tmp1) + 1)\n",
    "            return res \n",
    "\n",
    "\n",
    "        return f(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLines(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        total = (1 << n) - 1\n",
    "        \n",
    "        def is_line(p1, p2, p3):\n",
    "            x1, y1 = p1\n",
    "            x2, y2 = p2\n",
    "            x3, y3 = p3\n",
    "            return (x2-x1) * (y3-y1) == (x3-x1) * (y2-y1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if state == total:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for i in range(n):\n",
    "                if not (1 << i) & state:\n",
    "                    nxt_state = state | 1 << i\n",
    "                    for j in range(i + 1, n):\n",
    "                        cur = nxt_state | 1 << j\n",
    "                        for other in range(j + 1, n):\n",
    "                            if not (1 << other) & cur and is_line(points[i], points[j], points[other]):\n",
    "                                cur |= 1 << other\n",
    "                        ans = min(ans, dfs(cur) + 1)\n",
    "                    if i == n - 1:\n",
    "                        ans = min(ans, dfs(nxt_state) + 1)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 状压 + 记忆化递归\n",
    "    # 枚举点是否有直线了，再枚举没有直线的点和其他点组成直线\n",
    "    def minimumLines(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        total = (1 << n) - 1\n",
    "        \n",
    "        def is_line(p1, p2, p3):\n",
    "            x1, y1 = p1\n",
    "            x2, y2 = p2\n",
    "            x3, y3 = p3\n",
    "            return (x2-x1) * (y3-y1) == (x3-x1) * (y2-y1)\n",
    "\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if state == total:\n",
    "                return 0\n",
    "\n",
    "            ans = inf\n",
    "            for i in range(n):\n",
    "                if not (1 << i) & state:\n",
    "                    nxt_state = state | 1 << i\n",
    "                    for j in range(i + 1, n):\n",
    "                        cur = nxt_state | 1 << j\n",
    "                        for other in range(j + 1, n):\n",
    "                            if not (1 << other) & cur and is_line(points[i], points[j], points[other]):\n",
    "                                cur |= 1 << other\n",
    "\n",
    "                        ans = min(ans, dfs(cur) + 1)\n",
    "\n",
    "                    if i == n - 1:\n",
    "                        ans = min(ans, dfs(nxt_state) + 1)\n",
    "\n",
    "            return ans\n",
    "        \n",
    "        \n",
    "        return dfs(0)\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
